package com.shycloud.mido.organ.test.algorithms;

import com.alibaba.fastjson.JSONObject;
import com.google.gson.Gson;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Xiaoxing Yu
 * @date 2020/8/7
 **/
public class Permutation {
	/**
	 * 输入: [1,2,3]
	 * 输出:
	 * [
	 * [1,2,3],
	 * [1,3,2],
	 * [2,1,3],
	 * [2,3,1],
	 * [3,1,2],
	 * [3,2,1]
	 * ]
	 *
	 * 给定一个数字的序列，返回其所有可能的全排列。
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 3;
		int[] arr = new int[]{1,2,3};

		List<List<Integer>> result = new ArrayList<>();

		List<Integer> tempRes = new ArrayList();
		tempRes.add(arr[0]);
		search(tempRes, result, n, 0, arr, 0);

		System.out.println(JSONObject.toJSONString(result));
	}

	private static void search(List<Integer> tempRes, List<List<Integer>> result, int n, int count, int[] arr, int index) {
		if (count == n) {
			tempRes.add(arr[index]);
			result.add(tempRes);
			tempRes.remove(tempRes.size() - 1);
			return;
		}

		tempRes.add(arr[index]);

		for (int i = 0; i < arr.length; i++) {
			search(tempRes, result, n, count + 1, arr, i + 1);
		}
	}

}
